L'automate (D'après BAC ES, Amérique du Nord 2019) - Corrigé

Énoncé

Pour accéder à un local d'une petite entreprise, les employés doivent choisir un code reconnu par l'automate suivant :

Une succession de lettres constitue un code possible si ces lettres se succèdent sur un chemin du graphe orienté ci-dessus, en partant du sommet n° 1 et en sortant au sommet n° 4.

Par exemple :

• le mot  \(bcbab\)  est un mot reconnu par cet automate, et correspond au chemin  \(121334\)  ;
• le mot  \(abac\)  n'est pas reconnu par cet automate.

1. Parmi les mots \(abab, abc, abbcbb\) , quels sont ceux qui sont reconnus par cet automate ?

2. Écrire la matrice d'adjacence \(A\)  du graphe, en rangeant les sommets dans l'ordre croissant.

3. Quel est le nombre minimal de lettres d'un code possible ? Justifier.

4. Y a-t-il un nombre maximal de lettres d'un code possible ? Justifier.

5. On a calculé  \(A^4=\begin{pmatrix}5&3&10&5\\1&6&7&4\\1&3&4&2\\2&1&4&2\end{pmatrix}\)  et  \(A^5=\begin{pmatrix}3&15&18&10\\6&6&14&7\\3&4&8&4\\1&6&7&4\end{pmatrix}\)

    a. Combien y a-t-il de mots de quatre lettres qui conviennent ? Quels sont-ils ?
    b. Combien y a-t-il de mots de cinq lettres qui conviennent ?
    c. Pour varier les mots possibles, l'un des employés suggère de changer la programmation de l'automate pour utiliser dorénavant les chemins qui entrent au sommet n° 1 et sortent au sommet n° 2. Est-ce une bonne idée avec des mots de quatre lettres ? Avec des mots de deux lettres ?

\(\) Solution

1. Le mot  \(abab\)  est reconnu (chemin  \(12334\) ) ainsi que le mot  \(abbcbb\)  (chemin  \(1234234\)  ) mais le mot  \(abc\)  n'est pas reconnu. En effet, pour sortir au sommet n° 4, il faut terminer le mot par  \(b\) .

2. La matrice d'adjacence de ce graphe est  \(A=\begin{pmatrix}0&2&1&0\\1&0&1&0\\0&0&1&1\\0&1&0&0\end{pmatrix}\)

Cette matrice n'est pas symétrique car le graphe est orienté. Le coefficient  \(a_{1,2}=2\)  correspond aux deux arcs parallèles du sommet n° 1 vers le sommet n° 2.

3. Pour trouver le nombre minimal de lettres d'un mot, il faut calculer la distance entre les sommets n° 1 et n° 4. Pour cela, on peut calculer  \(A^2\)  dont le coefficient  \((1,4)\)  vaut  \(1\) , ou plus simplement on peut vérifier sur le graphe que le chemin  \(134\)  correspondant au mot  \(bb\)  permet de relier ces deux sommets.

4. Il n'y a pas de nombre maximal de lettres d'un mot, en raison de l'existence de cycles et même d'une boucle.

5. a. Le coefficient  \((1,4)\)  de la matrice  \(A^4\)  vaut 5, il y a donc cinq chemins possibles :

• chemin  \(12334\)  qui donne  \(abab\)  ;
• chemin  \(12334\)  en utilisant l'arc parallèle entre les sommets n° 1 et n° 2 qui donne  \(bbab\)  ;
• chemin  \(12134\)  qui donne  \(acbb\)  ;
• chemin  \(12334\)  en utilisant l'arc parallèle entre les sommets n° 1 et n° 2 qui donne  \(bcbb\)  ;
• chemin  \(13334\)  qui donne  \(baab\) . 

Tous ces mots sont différents donc il y a bien cinq mots possibles.

    b. Le coefficient  \((1,4)\)  de la matrice  \(A^5\)  vaut 10, il y a donc dix chemins possibles :

• chemins  \(123334\)  qui donnent  \(abaab\)  ou  \(bbaab\)  ;
• chemins  \(121334\)  qui donnent  \(acbab\)  ou  \(bcbab\)  ;
• chemins  \(121234\)  qui donnent  \(acabb\) ,  \(acbbb\) ,  \(bcabb\)  ou  \(bcbbb\)  ;
• chemin  \(134234\)  qui donne  \(bbcbb\)  ;
• chemin  \(133334\)  qui donne  \(baaab\) .

Tous ces mots sont différents donc il y a bien dix mots possibles. 

    c. Le coefficient  \((1,2)\)  de la matrice  \(A^4\)  vaut 3, il y a donc seulement 3 chemins possibles, ce qui donnera au maximum 3 mots possibles.
Ce n'est donc pas une bonne idée si on fixe la longueur des mots à quatre lettres, bien que la dernière lettre possible en arrivant sur le sommet n° 2 soit  \(a\)  ou  \(c\) , alors que seule  \(c\)  est possible en fixant l'arrivée au sommet n° 4.